Out-of-order microprocessors can provide improved computational performance by executing instructions in a sequence that is different from the order in the program, so that instructions are executed when their input data is available rather than waiting for the preceding instruction in the program to execute. In order to allow instructions to run out-of-order on a microprocessor it is useful to be able to rename registers used by the instructions. This enables the removal of “write-after-read” (WAR) dependencies from the instructions as these are not true dependencies. By using register renaming and removing these dependencies, more instructions can be executed out of program sequence, and performance is further improved. Register renaming is performed by maintaining a map of which registers named in the instructions (called architectural registers) are mapped onto the physical registers of the microprocessor.
However, the flow of instructions in a program can sometimes change during execution. For example, in the case of branch instructions, branch prediction is often used to predict which instruction branch will be taken, to allow the instructions in the predicted branch to be speculatively executed out-of-order. This means that branch mispredictions can occur, which can be realised after having sent many speculative instructions through the register renaming stage and into the execution pipelines. To allow the program flow to be reset and continue correctly after an incorrectly predicted branch is taken, the register renaming map is “rewound” to the state that it was in at the time that the mispredicted branch passed through the register renaming stage. Similar effects are also seen in the case that other instructions cause unexpected changes in program flow, such as interrupts or exceptions.
Current out-of-order processors enable the rewinding of the register renaming map by saving a snapshot of the register renaming map whenever an instruction that may be a flow risk goes through the register renaming stage (a flow risk here includes interrupts, exceptions, branches or any other instruction which may cause a change in the execution flow when it is executed). However, this requires the provision of a large amount of storage in which to save all the snapshots, because if all the snapshot storage is used then the instruction stream must be stalled until snapshots can again be saved, which compromises performance.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known out-of-order microprocessors.